//
//  Problem350.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 350. 两个数组的交集 II
 给定两个数组，编写一个函数来计算它们的交集。

 示例 1：
     输入：nums1 = [1,2,2,1], nums2 = [2,2]
     输出：[2,2]
 示例 2:
     输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     输出：[4,9]
 说明：
     输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
     我们可以不考虑输出结果的顺序。
 
 进阶：
     如果给定的数组已经排好序呢？你将如何优化你的算法？
     如果 nums1 的大小比 nums2 小很多，哪种方法更优？
     如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 */
@objcMembers class Problem350: NSObject {
    func solution() {
        print(intersectPoint([1,2,2,1], [2,2]))
        print(intersectPoint([4,9,5], [9,4,9,8,4]))
        
    }
    
    /*
     哈希表
     1: 将nums1变成map，key是值，value是个数
     2: 遍历nums2，如果在map中找到，个数-1，
     */
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var nMap:[Int:Int] = [:]
        for n in nums1 {
            nMap[n, default: 0] += 1
        }
        var result: [Int] = []
        for n in nums2 {
            if nMap[n] != nil {
                result.append(n)
                nMap[n]! -= 1
                if nMap[n] == 0 {
                    nMap[n] = nil
                }
            }
        }
        return result
    }
    
    /*
     双指针
     双指针的前提是：已排好序的数组
     1: 将2个数组排序
     2: 创建2个指针i，j，分别指向2个数组的开头
     3: 如果n[i] == n[j] 找到一个，其他的让小的那个++
     */
    func intersectPoint(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var result: [Int] = []
        
        let n1 = nums1.sorted()
        let n2 = nums2.sorted()
        var i = 0
        var j = 0
        while i < n1.count, j < n2.count {
            if n1[i] == n2[j] {
                result.append(n1[i])
                i += 1
                j += 1
                
            } else if n1[i] < n2[j] {
                i += 1
            } else {
                j += 1
            }
        }
        return result
    }
}
